Leetcode 1491

Since today's questions are too easy, we just put down the res for both weekly challange and daily challange.

1419

class Solution {
    public double average(int[] salary) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        int total = 0;
        for(int n : salary){
            min = Math.min(min,n);
            max = Math.max(max,n);
            total += n;
        }
        return (total - min - max) / (double)(salary.length - 2);
    }
}

1065

// the native apporach
class Solution {
    public int[][] indexPairs(String text, String[] words) {
        ArrayList<int[]> res = new ArrayList<>();
        Arrays.sort(words,(a,b) ->{return a.length() - b.length();}); // insure the order.
        for(int i = 0; i < text.length(); i ++){
            for(String word : words){
                if(text.substring(i).startsWith(word)){
                    res.add(new int[]{i,i + word.length() - 1});
                }
            }
        }
        int[][] ans = new int[res.size()][2];
        for(int i = 0; i < res.size(); i ++){
            ans[i] = res.get(i);
        }
        return ans;
    }
}

Because trie can detect a shorter word along the way, this avoid the sorting which can take extra time. this is a better solution.

class Solution {
    public class TrieNode{
        boolean word;
        TrieNode[] children;
        public TrieNode(){
            word = false;
            children = new TrieNode[26]; //26 character
        }
    }
    public class MyTrie{
        TrieNode root;
        public MyTrie(){
            root = new TrieNode();
        }
        public void add(String word){
            TrieNode curr = root;
            for(char c : word.toCharArray()){
                if(curr.children[c - 'a'] == null){
                    curr.children[c - 'a'] = new TrieNode();
                }
                curr = curr.children[c - 'a'];
            }
            curr.word = true;
        }
        public boolean serach(String word){
            TrieNode curr = root;
            for(char c : word.toCharArray()){
                if(curr.children[c - 'a'] == null) return false;
                curr = curr.children[c - 'a'];
            }
            return curr.word;
        }
        
    }
    public int[][] indexPairs(String text, String[] words) {
        MyTrie trie = new MyTrie();
        for(String word : words){
            trie.add(word);
        }
        List<int[]> res = new ArrayList<>();
        for(int i = 0; i < text.length(); i ++){
            TrieNode p = trie.root;
            for (int j = i; j < text.length(); j++) {
                if (p.children[text.charAt(j) - 'a'] == null) {
                    break;
                }
                p = p.children[text.charAt(j) - 'a'];
                if (p.word) {
                    res.add(new int[] { i, j });
                }
            }
        }
        int[][] ans = new int[res.size()][];
        ans = res.toArray(ans);
        return ans;
    }
}